#include <stdio.h>
#include <stdlib.h>

// 链表节点结构
typedef struct Node {
    int key;                // 键值
    struct Node* next;      // 指向下一个节点的指针
} Node;

// 哈希表结构
typedef struct HashTable {
    Node** table;           // 哈希表
    int size;               // 哈希表大小
} HashTable;

// 创建新节点
Node* createNode(int key) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->key = key;
    newNode->next = NULL;
    return newNode;
}

// 创建哈希表
HashTable* createHashTable(int size) {
    HashTable* ht = (HashTable*)malloc(sizeof(HashTable));
    ht->size = size;
    ht->table = (Node**)malloc(size * sizeof(Node*));
    
    for (int i = 0; i < size; i++) {
        ht->table[i] = NULL;  // 初始化每个槽位为空
    }
    
    return ht;
}

// 哈希函数
int hashFunction(int key, int size) {
    return key % size;  // 模运算作为哈希函数
}

// 插入元素
void insert(HashTable* ht, int key) {
    int index = hashFunction(key, ht->size);
    Node* newNode = createNode(key);
    
    // 将新节点插入到链表的开头，如果已存在，则初始化一个链表，否则，头插入 一个链表
    newNode->next = ht->table[index];//头插法
    ht->table[index] = newNode;//数组元素指向链表地址
}

// 查找元素
Node* search(HashTable* ht, int key) {
    int index = hashFunction(key, ht->size);
    Node* current = ht->table[index];//首先找到对应的链表，由 哈希值确定
    
    while (current != NULL) {//在链表中进行顺序查找
        if (current->key == key) {
            return current;  // 找到元素
        }
        current = current->next;
    }
    
    return NULL;  // 元素未找到
}

// 删除元素
void delete(HashTable* ht, int key) {
    int index = hashFunction(key, ht->size);
    Node* current = ht->table[index];
    Node* prev = NULL;
    
    while (current != NULL) {
        if (current->key == key) {
            if (prev == NULL) {
                // 删除头节点
                ht->table[index] = current->next;
            } else {
                // 删除中间或尾节点
                prev->next = current->next;
            }
            free(current);
            printf("Deleted key %d\n", key);
            return;
        }
        prev = current;
        current = current->next;
    }
    
    printf("Key %d not found for deletion\n", key);
}

// 打印哈希表
void printHashTable(HashTable* ht) {
    for (int i = 0; i < ht->size; i++) {
        Node* current = ht->table[i];
        printf("Index %d: ", i);
        while (current != NULL) {
            printf("%d -> ", current->key);
            current = current->next;
        }
        printf("NULL\n");
    }
}

// 主函数
int main() {
    HashTable* ht = createHashTable(11);

    insert(ht, 10);
    insert(ht, 22);
    insert(ht, 31);
    insert(ht, 4);
    insert(ht, 15);
    insert(ht, 28);
    insert(ht, 17);
    insert(ht, 88);
    insert(ht, 59);

    printf("Hash table after inserts:\n");
    printHashTable(ht);

    printf("Searching for key 22: %s\n", search(ht, 22) ? "Found" : "Not found");
    printf("Searching for key 100: %s\n", search(ht, 100) ? "Found" : "Not found");

    delete(ht, 22);
    printf("Hash table after deleting 22:\n");
    printHashTable(ht);

    // 释放内存
    for (int i = 0; i < ht->size; i++) {
        Node* current = ht->table[i];
        while (current != NULL) {
            Node* temp = current;
            current = current->next;
            free(temp);
        }
    }
    free(ht->table);
    free(ht);
    
    return 0;
}
